Search for: All records

In recent years, quantum computing involving physical systems with continuous degrees of freedom, such as the bosonic quantum states of light, has attracted significant interest. However, a well-defined quantum complexity theory for these bosonic computations over infinite-dimensional Hilbert spaces is missing. In this work, we lay the foundations for such a research program. We introduce natural complexity classes and problems based on bosonic generalizations of BQP, the local Hamiltonian problem, and QMA. We uncover several relationships and subtle differences between standard Boolean classical and discrete-variable quantum complexity classes, and identify outstanding open problems. Our main contributions include the following: 1) Bosonic computations. We show that the power of Gaussian computations up to logspace reductions is equivalent to bounded-error quantum logspace (BQL, characterized by the problem of inverting well-conditioned matrices). More generally, we define classes of continuous-variable quantum polynomial time computations with a bounded probability of error (CVBQP) based on gates generated by polynomial bosonic Hamiltonians and particle-number measurements. Due to the infinite-dimensional Hilbert space, it is not a priori clear whether a decidable upper bound can be obtained for these classes. We identify complete problems for these classes, and we demonstrate a BQP lower bound and an EXPSPACE upper bound by proving bounds on the average energy throughout the computation. We further show that the problem of computing expectation values of polynomial bosonic observables at the output of bosonic quantum circuits using Gaussian and cubic phase gates is in PSPACE. 2) Bosonic ground energy problems. We prove that the problem of deciding whether the spectrum of a bosonic Hamiltonian is bounded from below is co-NP-hard. Furthermore, we show that the problem of finding the minimum energy of a bosonic Hamiltonian critically depends on the non-Gaussian stellar rank of the family of energy-constrained states one optimizes over: for zero stellar rank, i.e., optimizing over Gaussian states, it is NP-complete; for polynomially-bounded stellar rank, it is in QMA; for unbounded stellar rank, it is RE-hard, i.e., undecidable. 

Abstract We prove that$${{\,\textrm{poly}\,}}(t) \cdot n^{1/D}$$ $\text{poly}\left(t\right)·n^{1/D}$-depth local random quantum circuits with two qudit nearest-neighbor gates on aD-dimensional lattice withnqudits are approximatet-designs in various measures. These include the “monomial” measure, meaning that the monomials of a random circuit from this family have expectation close to the value that would result from the Haar measure. Previously, the best bound was$${{\,\textrm{poly}\,}}(t)\cdot n$$ $\text{poly}\left(t\right)·n$due to Brandão–Harrow–Horodecki (Commun Math Phys 346(2):397–434, 2016) for$$D=1$$ $D=1$. We also improve the “scrambling” and “decoupling” bounds for spatially local random circuits due to Brown and Fawzi (Scrambling speed of random quantum circuits, 2012). One consequence of our result is that assuming the polynomial hierarchy ($${{\,\mathrm{\textsf{PH}}\,}}$$ $\mathrm{PH}$) is infinite and that certain counting problems are$$\#{\textsf{P}}$$ $\#P$-hard “on average”, sampling within total variation distance from these circuits is hard for classical computers. Previously, exact sampling from the outputs of even constant-depth quantum circuits was known to be hard for classical computers under these assumptions. However the standard strategy for extending this hardness result to approximate sampling requires the quantum circuits to have a property called “anti-concentration”, meaning roughly that the output has near-maximal entropy. Unitary 2-designs have the desired anti-concentration property. Our result improves the required depth for this level of anti-concentration from linear depth to a sub-linear value, depending on the geometry of the interactions. This is relevant to a recent experiment by the Google Quantum AI group to perform such a sampling task with 53 qubits on a two-dimensional lattice (Arute in Nature 574(7779):505–510, 2019; Boixo et al. in Nate Phys 14(6):595–600, 2018) (and related experiments by USTC), and confirms their conjecture that$$O(\sqrt{n})$$ $O\left(\sqrt{n}\right)$depth suffices for anti-concentration. The proof is based on a previous construction oft-designs by Brandão et al. (2016), an analysis of how approximate designs behave under composition, and an extension of the quasi-orthogonality of permutation operators developed by Brandão et al. (2016). Different versions of the approximate design condition correspond to different norms, and part of our contribution is to introduce the norm corresponding to anti-concentration and to establish equivalence between these various norms for low-depth circuits. For random circuits with long-range gates, we use different methods to show that anti-concentration happens at circuit size$$O(n\ln ^2 n)$$ $O\left(n{ln}^{2}n\right)$corresponding to depth$$O(\ln ^3 n)$$ $O\left({ln}^{3}n\right)$. We also show a lower bound of$$\Omega (n \ln n)$$ $\Omega (nlnn)$for the size of such circuit in this case. We also prove that anti-concentration is possible in depth$$O(\ln n \ln \ln n)$$ $O(lnnlnlnn)$(size$$O(n \ln n \ln \ln n)$$ $O(nlnnlnlnn)$) using a different model. 

The permanent is pivotal to both complexity theory and combinatorics. In quantum computing, the permanent appears in the expression of output amplitudes of linear optical computations, such as in the Boson Sampling model. Taking advantage of this connection, we give quantum-inspired proofs of many existing as well as new remarkable permanent identities. Most notably, we give a quantum-inspired proof of the MacMahon master theorem as well as proofs for new generalizations of this theorem. Previous proofs of this theorem used completely different ideas. Beyond their purely combinatorial applications, our results demonstrate the classical hardness of exact and approximate sampling of linear optical quantum computations with input cat states. 

We present a quasi-polynomial time classical algorithm that estimates the partition function of quantum many-body systems at temperatures above the thermal phase transition point. It is known that in the worst case, the same problem is NP-hard below this point. Together with our work, this shows that the transition in the phase of a quantum system is also accompanied by a transition in the hardness of approximation. We also show that in a system of n particles above the phase transition point, the correlation between two observables whose distance is at least Ω(logn) decays exponentially. We can improve the factor of logn to a constant when the Hamiltonian has commuting terms or is on a 1D chain. The key to our results is a characterization of the phase transition and the critical behavior of the system in terms of the complex zeros of the partition function. Our work extends a seminal work of Dobrushin and Shlosman on the equivalence between the decay of correlations and the analyticity of the free energy in classical spin models. On the algorithmic side, our result extends the scope of a recent approach due to Barvinok for solving classical counting problems to quantum many-body systems.